package DataStructure.tree;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 144. 二叉树的前序遍历 https://leetcode.cn/problems/binary-tree-preorder-traversal/
 * 题目简述：给你二叉树的根节点root，返回它节点值的前序遍历。
 * 前序遍历：根左右，即对于每一棵子树，先遍历其根节点，然后遍历其左子树，最后遍历其右子树
 */
public class PreorderTraversal {

    /**
     * 思路一：递归遍历。递归函数体：先访问树根节点，然后递归访问左子树，再递归访问右子树
     */
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        preTraversal(root,result);
        return result;
    }

    public void preTraversal(TreeNode root, List<Integer> result) {
        if(root == null) return;
        result.add(root.val);
        preTraversal(root.left, result);
        preTraversal(root.right, result);
    }

    /**
     * 思路二：非递归遍历。使用栈。循环体：指针一直向左走，经过就访问并压入栈。左为null则pop一个已访问元素出来，访问其右，如此循环，直到指针为null并且栈空
     */
    public List<Integer> preorderTraversal2(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (root != null || !stack.empty()) {
            while (root != null) {
                stack.push(root);
                result.add(root.val);//访问根节点
                root = root.left;//访问根节点的左子树
            }
            root = stack.pop();
            root = root.right;//访问右子树
        }
        return result;
    }
}
